Tropical Convexity via Cellular Resolutions

arXiv:math/0503279v3 [math.MG] 9 Jan 2006

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

FLORIAN BLOCK^ AND JOSEPHINE YU^

Abstract. The tropical convex hull of a hnite set of points in tropical
projective space has a natural structure of a cellular free resolution.
Therefore, methods from computational commutative algebra can be
used to compute tropical convex hulls. Tropical cyclic polytopes are
also presented.

1. Introduction

The tropical semiring (R, 0,0) is the set R of real numbers with two
binary operations called tropical addition © and tropical multiplication ©
dehned as

a © 6 = min{a, b), and a Q b = a + b, for all o, 6 G R.

Then R"" has the structure of a semimodule over the semiring (R, ©, 0) with
tropical addition

(xi, . . . ,Xn) © (yi, . . . ,yn) = (xi © yi, . . . ,Xn © Vn),

and tropical scalar multiplication

cQ{xi,...,Xn) = {cQXi,...,cQXn)-

A set A C R”" is called tropically convex if for all x,y € A and a, 6 G R also
(a © x) © (6 © y) G A. Notice that we do not put any extra condition on
a and b as in usual convexity. The tropical convex hull tconv(V) of a set
V C R” is the inclusionwise minimal, tropically convex set containing V in
R"". Also,

tconv(V) = {(ai©ui)©-■ ■©(ar©Ur) : ui,...,and oi,...,G R}.

Since any tropically convex set A is closed under tropical scalar multipli¬
cation, we identify it with its image under the projection onto the (n — 1)-
dimensional tropical projective space

TP”-i =R"/(1,...,1)R.

The tropical convex hull of a finite set of points has a natural structure of
a polyhedral complex. We refer to |2 for a more extensive introduction to
tropical convexity.

Date: December 31, 2005.

1991 Mathematics Subject Classification. 52A30, 13P99.

^ This work was carried out while visiting UC Berkeley from fall 2004 to spring 2005.
^ Corresponding author.

1

2

FLORIAN BLOCK AND JOSEPHINE YU

Let V = {vi,... ,Vr} C Vi = (vn,... ,Vin), and P = tconv(F).

Let S = , Xrn] be the polynomial ring over M with indeterminates

Xij for z G [r] = {1,..., r} and j G [n] = {1,... , n}. Let the weight of Xij be
Vij and the weight of a monomial G S' be ^ aijVij. The initial

form mv{f) of a polynomial f = Y1 CiX*^* is defined to be the sum of terms
CjX®* such that has maximal weight. Let J be the ideal generated by the
2x2 minors of the r x n matrix [xij]. Let I = iny(J) = (iny(/) \ f ^ J)
be the initial ideal of J with respect to V. If V is sufficiently generic, the
initial ideal / is a square free monomial ideal. The square free Alexander

1 k

dual I* of a square free monomial ideal I = (x® ,..., x® ) is

I* = n • • • n ,

where each a* is a 0-1 vector and mP = {xj : aj = 1). See iim for details.
The following is our main result.

Theorem 1. For a sufficiently generic set of points V in the tropical

convex hull V = tconviy) supports a minimal linear free resolution of the
ideal I*, as a cellular complex.

Moreover, the cellular structure of the minimal free resolution is unique
(Remark |2| , so we get the following algorithm for computing the tropical
convex hull of a finite set of points in tropical projective space.

Algorithm 2.

Input: A list of points vi,... ,Vr G TP*^”^ in generic position.
Output: The tropical convex hull of the input points.

Algorithm:

1. Set J = (2 X 2 minors of the r x n matrix [xij]).

2. Compute I = iny(J).

3. Compute the Alexander dual I* of I.

4. Find a minimal free resolution of I*.

5. Output the desired data about the tropical polytope.

A typical output for r = 4 and n = 3 is depicted in Figure ^ The ten grids
represent ten square free monomials in S of degree six, where each unshaded
box represents an indeterminate in the monomial. The cell complex is the
minimal free resolution of their ideal.

Since the set of 2 x 2 minors of a matrix is fixed under transposition of
the matrix, we immediately see the duality between tropical convex hulls of
r points in TP*^”^ and n points in TP*"”^, as shown in j2j.

The rest of this paper is organized as follows: In Section [21 we prove
Theorem ^ and demonstrate the algorithm with an example. In Section O
we deal with algorithmic and computational aspects. We suggest ways to
deal with non-generic points and to get an exterior (halfspace) description of
a tropical polytope. We also discuss the efficiency of Algorithm [21 Finally,
we study tropical cyclic polytopes in Section 0]

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

3

2. From Geometry to Algebra and Back

We first describe the polyhedral complex structure of the tropical poly¬
tope V. Let W = ]R'’+"/(l,... , 1, —1,... , —1)]R. Define an unbounded
polyhedron as follows:

Vv = {{y,z) -.yi + Zj < Vij for all i G [r],j G [n]}.

By El, there is a piecewise linear isomorphism between the complex of
bounded faces of Vv and the tropical polytope V = tconv(l/) given by
the projection (y, z) i—> 2 . The boundary complex dVy of Vy is polar to
the regular polyhedral subdivision of the product of simplices x A„_i
induced by the weights Vij. We denote this regular subdivision by (dVv)*-
More precisely, a subset of vertices {ei,ej) of A^-i x A„_i forms a cell of
the subdivision (dVv)* if and only if the equations yi + Zj = Vij indexed by
these vertices specify a face of the polyhedron Vy-

Let A denote the {r + n) x rn integer matrix whose column vectors are
the vertices {ei,ej) of A^-i x A„_i, where i G [r], j G [n]. This defines a
homomorphism Z™ —> by Cij i—> (cj, ej). Let L denote its kernel. The

ideal J generated by the 2x2 minors of [xij] is the (toric) lattice ideal

J = (x^ — : a, b G N™ with a — b G L).

See El Chapter 7] or ED Chapter 8] for details about lattice ideals.

Lemma 3. The initial ideal I is independent of the representatives of the
points Vi in the tropical projeetive spaee. In other words, if c- {1,1,... ,1) 'Is
added to any vt, the initial ideal I remains the same.

Proof. The ideal J is homogeneous with respect to any grading assigning
the same weight to the variables in each row. □

4

FLORIAN BLOCK AND JOSEPHINE YU

In the rest of this section, we will assume that the points vi,... ,Vr are in
generic position, i.e., they satisfy the conditions in the next result.

Proposition 4. The following are equivalent.

(1) The initial ideal I is a monomial ideal.

(2) The regular subdivision {dPy)* of Ar-ixAn-i induced by the weights
Vij is a triangulation.

(3) The polyhedron Vy is simple.

(4) For any k distinct points in V, their projections onto a k-dimensional
coordinate subspace do not lie in a tropical hyperplane, for any 2 <
k <n.

(5) No kxk submatrix of the rxn matrix \vij\ is tropically singular, i.e.,
has vanishing tropical determinant (e.g. see for any 2 < k < n.

Proof. (2) (3) follows directly from the polarity between the regular

subdivisions of A^-i x A„_i and dVy.

(2) (5) is proven in j2| Proposition 24],

(4) (5) is proven in j^l Lemma 5.1].

(1) (2): Statement (1) is equivalent to V being in the interior of a full

dimensional cone in the Grobner fan of the lattice ideal J. Statement (2)
means that V is in the interior of a full dimenional cone in the secondary
fan AA(E(.A)) which is the normal fan of the secondary polytope of A (for
details see [I^). By Proposition 8.15(a)], these two fans coincide if A
is unimodular, i.e., all invertible rank{A) x rank{A) submatrices have the
same determinant up to sign. We will check criterion (iv) of uni Theorem
19.3] for total unimodularity. Fix a collection of rows of A. Split it according
to containment in the upper r xrn submatrix of the (r + n) x rn matrix A.
Then the sum of the rows in each part is a 0-1 vector. This implies that all
submatrices of A have determinants 0 or ±1, so ^ is unimodular. □

It also follows from the unimodularity that all monomial initial ideals of
J are square free m Corollary 8.9]. Let Ay(J) be the initial complex of
J, i.e., the simplicial complex whose Stanley-Reisner ideal (see Emu) is
I = iny(J). We can identify a square free monomial m a S with the set
of indeterminates Xij dividing m. The vertices of Ay{ J) are Xij, and the
minimal generators of I are the minimal non-faces of Ay{,J). Moreover, the
minimal generators of the Alexander dual I* are the complements of the
maximal cells of Ay{J). The following lemma follows immediately from [HI
Theorem 7.33] or Theorem 8.3] and establishes a connection between
the ideal J and the tropical convex hull.

Lemma 5. We have an isomorphism Ay{J) = {dVy)* , as cell complexes.
In particular, there is a bijection between maximal cells of Ay (J) and those
of {dPy)* induced by Xij <—> {ei,ej).

We will label the vertices of Vy by the minimal generators of I* so that
Vy gives a cellular resolution of I*. First, we have a general lemma about
simple polyhedra which can be proved using [HI Proposition 4.5].

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

5

Lemma 6 ([HI Section 4.3.6 and Exercises 4.5-6]). Let P be a simple poly¬
hedron (possibly unbounded) with facets Fi,..., Fm- Label each face G of
P by ^ • • • ,Xm]- Then the complex of bounded faces

of P supports a minimal linear free resolution of the square free monomial
ideal generated by the vertex labels.

We will apply this to Vy to prove Theorem ^stated in the introduction.

Proof of Theorem^ Since V is generic, Vy is simple. Hence, by Lemma El
the tropical convex hull V, which is isomorphic to the complex of bounded
faces of Vy, supports a minimal linear free resolution of the ideal generated
by the monomial labels of its vertices. We only need to show that the labels
from Lemma El coincide with the minimal generators of I*.

The facets Fij of Vy are defined by equations yi -|- Zj = Vij. Let Xij be
the indeterminate corresponding to F^j. For a square free monomial m,

m is a vertex label of Vy

^ rn^« : Xij does not divide m} is a vertex of Vy

{{ei,ej) : Xij does not divide m} is a maximal cell of {dVy)*

{xij : Xij does not divide m} is a maximal cell of Ay(J)
m is a minimal generator of I*.

The third equivalence follows from Lemma El D

Remark 7. By construction, the monomial labels are unique, so all the
multi-graded Betti numbers are at most one. This combined with the lin¬
earity of the resolution implies that the cellular structure of the minimal
free resolution is unique.

However, the multi-graded Betti numbers already determine the tropical
polytope because in this case a face F contains a face G if and only if the
monomial label of F is divisible by the monomial label of G. Moreover,
the vertex labels (the minimal generators of I*) determine all the other
monomial labels by Lemma IT^

The dimension dim{U) of any subset Lf of is the affine dimension

of its projection {u G M” : ( 0 , u) G C/} onto the last n — 1 coordinates.

Corollary 8. For any face F <ZV, dim{F) = deg(x.^^) — (n — l)(r — 1).

Figure 2. Grids representing X 2 iX 22 X‘siX‘i 2 XiiX 42 and
X 11 X 13 X 31 X 33 X 41 X 42 for r = 4, n = 3. These are the labels
of vi and V 2 in Figure ^

6

FLORIAN BLOCK AND JOSEPHINE YU

The monomial labels have a geometric meaning. To have a more intuitive
notation, we will represent each squarefree monomial m G S' with an r x re
grid shaded at position {i,j) if Xij does not divide m. Hence the support of
is left unshaded in the grid (see Figure l2j. Let Cj = cone{ei ■ i ^ j}
be the closed cone which is the usual conical (positive) hull of all but one
standard unit vector. Suppose z = {zi,..., Zn) G P is in the relative interior
of a cell with label and it is the image of the point (y, z) G Vy- Then

I'lj

Vi + Zj = Vij

yi + zk<v

UU

So the box {i,j) is shaded if and only if the input vertex Vi lies in the sector
z + Cj. See Figure Otb).

This monomial labeling is essentially the same as the labeling by types
introduced in |2j. Specifically, for any point z in the relative interior of a
cell F m. V with type(z) = (Si,..., S^), we have i G Sj if and only if Xij
does not divide x*^^. The following result follows from [21 Lemma 10].

Lemma 9. Given the monomial label x®^ of a vertex z, its eoordinates ean
be computed by solving the linear system

{zi — Zk = Vii — Vik : i G [r], k,l & [re], Xik and xu do not divide x®^}.

Example 10. (Four Points in TP^.) Assume we are given the following
points in TP^ (r = 4, re = 3):

VI = (0,3,4), U 2 = (0, 5, 2), us = (0,1,1), U 4 = (0,4, -1).

They determine the tropical polytope in Figure ^ The points give the
weight vector V = (0, 3,4, 0, 5, 2,0,1,1, 0,4, —1) in the polynomial ring S =
^[xii,xi 2 ,xi^,X 2 i,X 22 iX 2 ^,xzi, X 32 , X 33 , X 41 , X 42 , 0 : 43 ]• The initial ideal I and
its Alexander dual are

xii a;i2 xi3

X 21 X 22 X 23

2^31 2:32 2:33

2^41 2:42 2:43

(2^332-41 7 2^23 2^41 ? 2^232-317 2^122^317 2^312^ 112-42 7 2^112-42 7 2^312^417 2^312^317 2^1321217

2^332142,2:22 2;4 i, 2 ;i 32;327 21222:317 21ii2;22, 2:232:42,2:222:33,2:132:42,2:132:22,2:122:212:33),
I* = {X 12 X 13 X 22 X 23 X 33 X 42 , X 12 X 13 X 22 X 23 X 41 X 42 , X 13 X 22 X 23 X 31 X 33 X 42 ,

Xl2Xl3X22X3lX4iX42,Xi3X22X3lX33X4iX42,Xi3X2lX22X3lX4iX42,

I = illy (2x2 minors of

2:112:132:222:232:312:33,2:212:222:312:322:412:42,2:112:132:312:332:412:42,

2:ii2:i32:232:3i2;332:4i).

Note that I is not generated in degree 2. Compare the minimal generators
of I* with the grids in Figure ^ The minimal free resolution of I* is of the
form

^10 ^12 ^3

0

0 .

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

7

The tropical convex hull consists of 10 zero-dimensional faces (vertices), 12
one-dimensional faces (edges), and 3 two-dimensional faces.

Tabled shows the monomial matrix M 2 in the monomial matrix notation
of jni Section 1.4], The rows correspond to the edges of the tropical polytope,
and the three columns, whose labels are omitted here, correspond to the faces
/i,/ 2 , and /a, respectively.

Xl2Xi3X22X23X3lX33^i2

X12X13X22X23X33X4IX42

X12X13X22X23X31X41X42

X12X13X22X31X33X41X42

X11X13X22X23X31X33X42

X 12 X 13 X 21 X 22 X 31 X 41 X 42

X 13 X 22 X 23 X 3 IX 33 X 4 IX 42

X 13 X 21 X 22 X 31 X 32 X 41 X 42

X11X13X22X31XS3X41X42

X13X21X22X31X33X41X42

X11X43X22X23X31X33X44

2:11X130:230:31X33X41X42

- 1 0 0 -

-10 0

-10 0

-110
0 0-1

0-10
10-1
0 0 0

0 0 1

0 10

0 0-1

. 0 0 1 .

Table 1. Monomial matrix M 2 in Example 1101

3. Algorithmic and Computational Aspects

Let 0 <—/*<— Fq <—••• <— Fm be the free resolution computed by the
algorithm, and let Mj : Fi —> Fj_i denote the monomial matrices defining
the boundary maps. Since the free resolution is linear, the row labels of the
matrix Mj are in one-to-one correspondence with the faces of dimension i — 1,
its column labels with the faces of dimension i. An entry in Mj is nonzero if
and only if its row label divides its column label, which happens if and only
if the face corresponding to its column contains the face corrresponding
to its row. Therefore the number of i-dimensional faces with k facets in
the tropical convex hull is equal to the number of columns of Mj having k
nonzero entries. A face F is maximal if and only if it has dimension n — 1
or the row in M^j^(p)+i labeled by contains zeroes only. So the eighth
row in Table ^ corresponds to edge e in Figure ^ which is not contained in
any other face.

We can also compute the f-matrix [fij] {0 < i < n —1,1 < j) where fij is
the number of faces having dimension i and j vertices. We already know the
/-vector fij which is the sum of columns in the /-matrix. The following
result in was obtained by counting regular triangulations of A^-i x A„_i.

Proposition 11 ([^ Corollary 25]). All tropical convex hulls of r generic
points in have the same f-vector. The number of faces of dimension

i is equal to the multinomial coefficient

( r-\-n — i — 2 \ (r-|-n —i —2)!

r — i — l,n — i — l,ij [r — i — 1)\ ■ [n — i — 1)\ ■ i\

FLORIAN BLOCK AND JOSEPHINE YU

A Combinatorial Algorithm for Building the Face Poset. Given the
vertex labels of P, we can compute the whole face poset of V combinatorially.
The following result follows from [2l Corollary 14] and Corollary |H1

Lemma 12. Let F he a face ofV with grid ap and let b be a grid arising from
ap by unshading one box such that no row or column is completely unshaded.
Then there is a face G D F with label ac = b and of one dimenstion higher.

Conversely, every face can be obtained this way starting from the vertices.
So, instead of computing the free resolution, we can build the fact poset
combinatorially if we know the vertex labels, i.e., the minimal generators
of I*. We have an implementation of this algorithm using Macaulay 2 |2j,
Maple |Hj, and JavaView |Hj.

Remark 13 (Non-generic Input Vertices). When the input vertices V are
not in generic position, the initial ideal I is not monomial. In that case, we
can replace the weights V with any refinement which makes I a monomial
ideal and proceed as before to build the face poset. We can then compute
the coordinates of the vertices using LemmaEland identify vertices with the
same coordinates. We suggest this algorithm without having a proof.

Tropical Halfspaces. Tropical halfspaces introduced in [1] give us an ex¬
terior description of tropical polytopes. We can extend our algorithm to
find such a description.

C2

1

u

0

/

/

C3

(b)

Figure 3. (a) Tropical hyperplane in TP^ with apex a.

(b) The sectors at apex 0 in TP^. (c) Tropical halfspace
(a, {1,2}) in TP^.

The tropical hyperplane at the apex a € TP” ^ is the set which is the
union of boundaries of the sectors a + Ci (see Figure inj. For a G TP"

0 7 ^ A C [n], the set a + UigA ^ closed tropical halfspace (see Figure
Etc)). Tropical halfspaces are tropically convex, and a tropical polytope
V is the intersection of the inclusionwise minimal halfspaces containing it
[^. The apex of such a minimal halfspace must be a vertex of V on the
boundary [H Lemma 3.6]. Recall that the box (i,j) in the grid label of a
vertex v is shaded if and only if Uj G u -t- Cj. Hence V is the intersection of
the halfspaces v -|- UigA such that u is a vertex of V and A is a minimal
subset of columns in the corresponding grid of v such that the shaded boxes

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

9

in those column cover all the rows. This description is redundant in general.
We may be able to refine this result as follows.

Conjecture 14. In the generic case, a minimal half space with respect to

V has the form v + UieA where v is a vertex of V and in the grid label of

V the shaded boxes in the columns in A form a partition of [r].

The converse of the conjecture above is not true, i.e., there are non-
minimal halfspaces of the form described.

Experiments with Computation Time. We experimented with com¬
puting tropical cyclic polytopes Cr^n (which will be defined in the next
section) with r input vertices in n — 1 (projective) dimensions. We used
Macaulay 2 jH] on a Sun Blade 150 (UltraSPARC-IIe 550MHz) computer
with 512MB memory. The computation became infeasible when rn > 80
or so, although r = 30, n = 3 worked. The main problem was the insuffi¬
cient amount of memory. Some sample computation times for tropical cyclic
polytopes are given in Table [2 We see from the data that computing the
Alexander dual can be a problem. This can be made faster using the Monos
Language for Monomial Decompositions [Tj-

n

r

Initial ideal

Alexander dual

Free resolution

3

30

74

433

2

4

21

64

944

23

6

10

15

221

27

8

10

70

4169

1106

Table 2. Computation times (in seconds) for I, I*
free resolution for tropical cyclic polytopes Cr^n-

and the

4. Tropical Cyclic Polytopes

Define tropical cyclic polytopes as Cr,n = tconvjui,..., u,.} C
where Vij = (i—l)(j —1) fori G [r], j G [n]. Since (i—1)®^'^“^) = (i—l)(j —1),
this is tropical exponentiation. The Cr^n are generic because the minimum in
any k x k minor of the matrix [vij] is attained uniquely by the antidiagonal.
An example of a tropical cyclic polytope is shown in Figure [IJa).

The 2x2 minors of [xij] form a Grobner basis with respect to V, and the
initial ideal I is the diagonal initial ideal generated by the binomials which
are on the diagonals of the 2x2 minors. This correspond to the staircase
triangulation of A^-i x A„_i.

Consider a path in an r x n grid representing indeterminates Xij, which
goes from the lower left corner to the upper right corner, only moving ei¬
ther right or up at each step as in Figure 0)b). Such paths are precisely
the maximal sets, with respect to inclusion, that do not contain diagonal
pairs. Hence their complements correspond to the minimal generators of the
Alexander dual I*, which are the monomial labels of the vertices of Cr^n-

10

FLORIAN BLOCK AND JOSEPHINE YU

Yi

...

X|„

:

:

:

Xr2

...

Xn,

(b)

Figure 4. (a) Tropical cyclic polytope on four vertices in
TP^. (b) A path corresponding to a generator of the Alexan¬
der dual I*.

Figure 5. (a) Paths in grids corresponding to two 1-valent
vertices in Cr^n- (b) Horizontal and vertical stripes.

The labels of the faces of the tropical cyclic polytope C'r,n are obtained
by unshading the boxes on the paths so that the remaining shaded set still
intersects every row and every column. For example, there are two 1-valent
vertices with grids corresponding to the paths in Figure Efa). The two
edges containing these vertices are the only maximal 1-faces, whose labels
are obtained by unshading the lower right corner and the upper left corner,
respectively.

We can identify a vertex of Cr^n with the Young diagram above (or below)
the corresponding path in the r x n grid. Then the 1-skeleton of Cr,n is
the Hasse diagram of the Young lattice of the Young diagram fitting in an
(r — 1) X (n — 1) grid.

The shaded part in the label of a fc-dimensional face contains the diagonal
steps as in Figure IHK a) exactly k times because every time we shade in such
a corner, the dimension decreases by one. By straightforward counting, we
get that

# fc-faces in Cr,n = (

\r — k — l,n — k — 1, kJ

TROPICAL CONVEXITY VIA CELLULAR RESOLUTIONS

11

Figure 6. (a) A diagonal step, (b) Corners indicating that
the corresponding monomials are not minimal.

as seen in Proposition 11 1 1 That is, out of the r + n — k — 2 steps we take
from the lower left corner to the upper right corner, we take r — k — 1 steps
up, n — A: — 1 steps right, and k steps diagonally.

Proposition 15. The exponential generating function for the numbers
of maximal k-faces of the tropical cyclic polytope Cr,n is

E

T 71 k ^ ( ( T \ 'll \ \

___X y z =—-y + xe^-x-xyj),
r\n\k\ oz

r>l,n>l,fc>0

and the ordinary generating function is

Vi-y / V Vi-2/

r>l,n>l,k>0

-y ^-x

Proof. A face is maximal if and only if the set of shaded boxes in the r x n
grid does not contain any corners as in Figure Etb). Then Mr^n,k is equal to
the number of {k + l)-tuples of either horizontal or vertical stripes of boxes,
as in Figure Efb) , such that the sum of the widths equals n and the sum of
heights equals r. The proposition follows from basic properties of generating
functions. □

Moreover, every fc-dimensional face contains precisely 2^ vertices because
every diagonal step as in Figure Efa) gives 2 ways of shading in the cor¬
ners, and there are exactly k such diagonal steps. From this it is easy
to see that every fe-dimensional face has the combinatorial structure of a
fe-dimensional hypercube. Therefore, the /-matrix of Cr,n is very simple:
fk, 2 k = (r-fc-pn-fc-i,fc)’ entries are 0.

5. Conclusion and Future Directions

The methods we described can be applied to a wide range of combinatorial
objects which are dual to triangulations of polytopes. For example, tight
spans of finite metric spaces can be computed using the 2x2 minors of
a symmetric matrix. There are also many enumerative questions about
tropical polytopes. For example, very little is known about the /-matrices.

12

FLORIAN BLOCK AND JOSEPHINE YU

6. ACKNOWLEDGEMENT

This paper grew out of a term project from the course “Combinatorial
Commuative Algebra” taught by Bernd Sturmfels at UC Berkeley in the
fall semester 2004. We are very grateful to Bernd Sturmfels for all his guid¬
ance, stimulating discussions, and inspiring questions. We also thank Mike
Develin, Hiroshi Hirai, Michael Joswig, David Speyer, and the referees for
helpful comments and suggestions. Florian Block held a DAAD scholarship,
and Josephine Yu was supported by an NSF Graduate Research Fellowship.

References

[1] D. Eisenbud, Commutative Algebra with a View toward Algebraic Geometry, Graduate
Texts in Mathematics, Springer, 1995.

[2] M. Develin and B. Stnrmfels, “Tropical Convexity”, Documenta Math. 9 (2004): 1-27.

[3] D. R. Grayson and M. E. Stillman, Macaulay 2, a software system for research in
algebraic geometry, 2002. Available at http://www.math.uiuc.edu/Macaulay2/

[4] M. Joswig, “Tropical Halfspaces”, arXiv: math.CO/0312068, 2003.

[5] Maple. Available at http://maplesoft.com

[6] E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Graduate Texts in
Mathematics, Springer, 2004.

[7] R. A. Milowski, Computing Irredundant Irreducible Decompositions of Large Scale
Monomial Ideals, ISSAC 2004, Santanders, Spain, 2004. Software available at
http://milowski.org/software.html

[8] K. Polthier, JavaView, a 3D geometry viewer and a mathematical visualization soft¬
ware. Available at http://www.javaview.de

[9] J. Richter-Gebert, B. Sturmfels, and T. Theobald, “First Steps in Tropical Geome¬
try”, Idempotent Mathematics and Mathematical Physics, Proceedings Vienna 2003,
American Mathematical Society, 2004.

[10] A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.

[11] B. Sturmfels, Grobner Bases and Convex Polytopes, University Lecture Series 8, Prov¬
idence: AMS, 1996.

Florian Block

Technische Universitat Munchen, Zentrum Mathematik, Boltzmannstr. 3,
85748 Garching, Germany

E-mail address: block@in.tum.de

Josephine Yu

Department of Mathematics, University of California, Berkeley, CA 94720

E-mail address: jyu@math.berkeley.edu